package com.zyk.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author zhangsan
 * @date 2021/4/16 15:04
 */
public class C315 {


    int[] ans;          // 答案数组
    int[] help;         // 排序辅助数组
    int[] index;        // 下标数组, 排序前每个数的下标
    int[] helpIndex;    // 辅助下标数组

    // https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/
    // 归并解
    public List<Integer> countSmaller(int[] nums) {
        // 答案list, 辅助数组(避免在每次归并的时候都要新开辟数组浪费空间),
        ans = new int[nums.length];
        help = new int[nums.length];
        index = new int[nums.length];
        helpIndex = new int[nums.length];

        for (int i = 0; i < nums.length; i++) index[i] = i;

        mergeSort(nums, 0, nums.length - 1);

        List<Integer> result = new ArrayList<>();
        for (int i : ans) result.add(i);
        return result;
    }

    private void mergeSort(int[] nums, int l, int r) {
        if (l == r) return;
        int m = l + ((r - l) >> 1);
        mergeSort(nums, l, m);
        mergeSort(nums, m + 1, r);
        if (nums[m] <= nums[m + 1]) return;    // 如果左边最大都比右边最小要小, 就已经都是有序不用合并了
        merge(nums, l, m, r);
    }

    private void merge(int[] nums, int L, int m, int R) {
        int i = L, j = m + 1, p = L;  // i:左边范围的指针, j右边范围的指针, p:辅助数组赋值的指针
        while (i <= m && j <= R) {
            if (nums[i] <= nums[j]) {    // <= 一定是左边先回去, 如果相等右边回去的话,左边收集答案时可能错过值
                help[p] = nums[i];              // 辅助换位
                helpIndex[p] = index[i];
                ans[index[i]] += (j - m - 1);   // 收集答案
                i++;
                p++;
            } else {     // 右边回去就只是回去
                help[p] = nums[j];
                helpIndex[p++] = index[j++];
            }
        }
        // 出来有两种情况: 左边越界, 右边越界
        while (i <= m) {
            help[p] = nums[i];              // 辅助换位
            helpIndex[p] = index[i];
            ans[index[i]] += (j - m - 1);   // 收集答案
            i++;
            p++;
        }
        while (j <= R) {
            help[p] = nums[j];
            helpIndex[p++] = index[j++];
        }
        // 把数组排序
        for (p = L; p <= R; p++) {
            index[p] = helpIndex[p];    // 每排好序, 他们的下标也得跟着换
            nums[p] = help[p];          // 排回去
        }
    }

    // 给的一个从小到大的升序数据, 插入动作直接变成O(N), 每次插入都要O(N), 时间复杂度卡死了.
    // 搜索二叉树解: 插入树的时候计算所有必当前节点小的节点的数量
    // 逆序插入统计比当前节点小的节点个数, 然后最后把答案做个反转
    /*public List<Integer> countSmaller2(int[] nums) {
        List<Integer> ans = new ArrayList<>();

        TreeNode root = new TreeNode(nums[nums.length - 1]);
        ans.add(0);
        for (int i = nums.length - 2; i >= 0; i--)
            ans.add(add(root, new TreeNode(nums[i])));
        Collections.reverse(ans);
        return ans;
    }

    // 添加后, 返回当前比它小的节点的数量
    private int add(TreeNode root, TreeNode newNode) {
        int smallCount = 0;
        if (root.val < newNode.val) {        // 比我大
            smallCount += root.leftCount + 1;
            if (root.right != null)
                smallCount += add(root.right, newNode);
            else
                root.right = newNode;
        } else {         // <=我
            root.leftCount += 1;
            if (root.left != null)
                smallCount += add(root.left, newNode);
            else
                root.left = newNode;
        }
        return smallCount;
    }

    // 例子中没有重复数, 如果有重复数的话, 可以加上当前节点有多少个.
    // 因为不能破坏搜索树的性质.
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        int leftCount;      // 左边节点的数量, 即必当前节点小的数量

        public TreeNode(int val) {
            this.val = val;
        }
    }*/

    /*public List<Integer> countSmaller2(int[] nums) {
        List<Integer> ans = new ArrayList<>();

        TreeNode root = new TreeNode(nums[nums.length - 1]);
        ans.add(0);
        TreeNode cur = null;
        for (int i = nums.length - 2; i >= 0; i--) {
            cur = new TreeNode(nums[i]);
            root = add(root, cur, 0);
            ans.add(cur.ans);
        }
        Collections.reverse(ans);
        return ans;
    }
    *//** 右旋 *//*
    private TreeNode rightRotate(TreeNode cur) {
        TreeNode left = cur.l;
        cur.l = left.r;
        left.r = cur;
        left.size = cur.size;
        cur.size = (cur.l == null ? 0 : cur.l.size) + (cur.r == null ? 0 : cur.r.size) + 1;
        return left;
    }
    *//** 左旋 *//*
    private TreeNode leftRotate(TreeNode cur) {
        TreeNode right = cur.r;
        cur.r = right.l;
        right.l = cur;
        right.size = cur.size;
        cur.size = (cur.l == null ? 0 : cur.l.size) + (cur.r == null ? 0 : cur.r.size) + 1;
        return right;
    }
    *//**
     * 维护这棵树的平衡, 违规情况有四种 ll, lr, rl, rr
     * 通过旋转进行平衡, 并递归维护修改过节点数量的节点
     * @param cur 当前树
     * @return 这棵树平衡后新的头
     *//*
    private TreeNode maintain(TreeNode cur) {
        if (cur == null)
            return null;
        int ls = 0, lls = 0,lrs = 0, rs = 0, rls = 0,rrs = 0;
        if(cur.l != null) {
            ls = cur.l.size;
            lls = cur.l.l == null ? 0: cur.l.l.size;
            lrs = cur.l.r == null ? 0: cur.l.r.size;
        }
        if( cur.r != null ) {
            rs = cur.r.size;
            rls = cur.r.l == null? 0 : cur.r.l.size;
            rrs = cur.r.r == null? 0 : cur.r.r.size;
        }
        if( lls > rs ) {
            // lls一次右旋
            cur = rightRotate(cur);
            cur.r = maintain(cur.r);
            cur = maintain(cur);
        }else if( lrs > rs ) {
            // lrs 孙子节点变爷爷
            cur.l = leftRotate(cur.l);
            cur = rightRotate(cur);
            // 变动的节点在调整从小往上调
            cur.l = maintain(cur.l);
            cur.r = maintain(cur.r);
            cur = maintain(cur);
        }else if( rrs > ls ) {
            // rrs一次左旋
            cur = leftRotate(cur);
            cur.l = maintain(cur.l);
            cur = maintain(cur);
        }else if(rls > ls) {
            // rls 孙子节点变爷爷
            cur.r = rightRotate(cur.r);
            cur = leftRotate(cur);
            // 变动的节点在调整从小往上调
            cur.l = maintain(cur.l);
            cur.r = maintain(cur.r);
            cur = maintain(cur);
        }
        return cur;
    }

    *//**
     * 添加节点
     * @param root 在哪儿棵树上添加
     * @param cur 要添加的节点
     * @param ans 当前的节点的答案
     * @return 返回添加后当前这棵树维护平衡后的新头部
     *//*
    private TreeNode add(TreeNode root, TreeNode cur, int ans) {
        if(root == null) {
            cur.ans = ans;
            return cur;
        }else {
            root.size++;
            if(cur.val < root.val) {       // 左边添加
                root.leftCount += 1;
                root.l = add(root.l, cur, ans);
            }else {                 // 右边添加, 收集一下答案.
                root.r = add(root.r, cur, ans + root.leftCount + 1);
            }
            return maintain(root);   // 维护平衡
        }
    }

    // 用sb树加个调平的操作
    public static class TreeNode {
        int val;
        TreeNode l;         // 左节点
        TreeNode r;         // 右节点
        int size;           // 当前树的大小
        int leftCount;      // 为了做题的属性, 左边节点的数量, 即必当前节点小的数量
        int ans;            // 为了做题的属性, 自己一路加到某个位置统计这一路比他小的节点数量

        public TreeNode(int val) {
            this.val = val;
            size = 1;
            ans = 0;
        }
    }*/

    // for test
    public static void main(String[] args) {
        C315 test = new C315();

//        int[] nums = {5, 2, 6, 1, 2, 45, 31, 5321, 532, 132, 132, 1, 313, 1, 31, 3, 13, 21, 6532, 13};
        int[] nums = {6, 5, 3, 7, 1, 2};
        int[] nums2 = Arrays.copyOf(nums, nums.length);
        /*List<Integer> ans = test.countSmaller2(nums);
        System.out.println(ans);*/
        List<Integer> ans2 = test.countSmaller(nums2);
        System.out.println(ans2);
    }

}
